package com.example.demo.leetcode.top;

/**
 * @author xujimou
 * @version 2.0
 * @Description
 * 给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
 *
 * 返回被除数 dividend 除以除数 divisor 得到的商。
 *
 * 整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
 *
 *  
 *
 * 示例 1:
 *
 * 输入: dividend = 10, divisor = 3
 * 输出: 3
 * 解释: 10/3 = truncate(3.33333..) = truncate(3) = 3
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/divide-two-integers
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @date 2022/1/27 16:00
 */
public class Test_两数相除 {


    /**
     * @Desciption:
     *  思路: 实现除法?
     *  定义函数 div(dividend, divisor)
     *  定义 tb = divisor   count =1
     *  每次 tb*2 < dividend ? count*2 : count
     *  最后 dividend - tb , 递归调用函数 div()+count
     *
     * @param dividend:
     * @param divisor:
     */

    public static int divide(int dividend, int divisor) {

        if(divisor == 0){
            return 0;
        }
        if(divisor == 1){
            return dividend;
        }
        if(divisor == -1){
            if(dividend>Integer.MIN_VALUE){
                return -dividend;
            }
            return Integer.MAX_VALUE;
        }

        int sign = -1;
        long a = dividend;
        long b = divisor;
        if((a > 0 && b >0) ||(a <0 && b < 0)){
            sign = 0;
        }
         a = a > 0 ? a : -a;
         b = b > 0 ? b : -b;
        long result = div(a, b);
        return (int) (sign == 0 ? result : -result);
    }

    public static long div(long a,long b){
        if(b>a) return 0;
        long b2 = b;
        long count = 1;
        while(a >= b2){
            count = count + count;
            b2 = b2 + b2;
        }
        count = count / 2;
        b2 = b2 / 2;
        return count + div(a-b2,b);
    }




    public static void main(String[] args) {
        long begin =System.currentTimeMillis();
        System.out.println(divide(-2147483648,2));
        System.out.println("cost:"+ (System.currentTimeMillis() - begin));
    }


}
